线段树在维护区间时可以维护任何区间信息，比如，一个单调栈。
题意：维护全局最大上升序列大小。
更新
线段树当前节点存储整个区间的最大值，对于该题，左子树的区间答案可以直接继承，然后用左子树区间的最大值查询右子树的答案并记录在该节点上。
1
2
3
4
5
6
| void update(const int &x,const double &k,const int &ro=1,const int &l=1,const int &r=n){
if(l==r) return ans[ro]=1,mx[ro]=k,void();
x<=mid?update(x,k,ls,l,mid):update(x,k,rs,mid+1,r);
mx[ro]=max(mx[ls],mx[rs]);
ans[ro]=ans[ls]+query(mx[ls],rs,mid+1,r);
}
|
其中，查询右区间比传的值大的节点个数的查询方式如下：
1
2
3
4
5
6
| int query(const double &k,const int &ro=1,const int &l=1,const int &r=n){
if(mx[ro]<=k) return 0;
if(l==r) return mx[ro]>k;
if(mx[ls]<=k) return query(k,rs,mid+1,r);
else return query(k,ls,l,mid)+ans[ro]-ans[ls];
}
|
维护后缀答案最小值。比较值为原序列，答案维护最小值。
1
2
3
4
5
6
| void update(const int &x,const int &ro=1,const int &l=1,const int &r=n){
if(l==r) return mx[ro]=a[x],void();
x<=mid?update(x,ls,l,mid):update(x,rs,mid+1,r);
mx[ro]=max(mx[ls],mx[rs]);
mn[ro]=query(mx[rs],ls,l,mid);
}
|
1
2
3
4
| int query(const int &k,const int &ro=1,const int &l=1,const int &r=n){
if(l==r) return mx[ro]>k?k+l:INF;
return k<mx[rs]?min(mn[ro],query(k,rs,mid+1,r)):query(k,ls,l,mid);
}
|
